package com.cn.codebrush.动态规划;

/**
 * @Author Boolean
 * @Date 2022/5/16 11:34
 * @Version 1.0
 */
public class No经典01背包问题 {
    /**
     * 问题描述：
     * 现有4个物品，小偷背包的容量为8，怎么样能偷到价值最多的东西？
     * 如：
     * 物品表号： 1  2  3  4
     * 物品重量： 2  3  4  5
     * 物品价值： 3  4  5  8
     */
    public static void main(String[] args) {
        int[] nums1 = {2,3,4,5};
        int[] nums2 = {3,4,5,8};
        System.out.println(rob(nums1,nums2,8));
    }

    /**
     * 1. 动态规划  01背包问题
     * 画表格可以辅助理解
     * @param nums1
     * @param nums2
     * @param sum
     * @return
     */
    public static int rob(int[] nums1, int[] nums2, int sum){
        int len1 = nums1.length;
        int[][] dp = new int[len1][sum+1];  //价值
        for(int i=0;i<len1;i++){
            for(int j=0;j<=sum;j++){  //注意这里的j<=sum  数组下标与容量相对应
                if(nums1[i] > j){
                    if(i==0){  //初始化边界
                        dp[i][j] = 0;
                    }else{
                        dp[i][j] = dp[i-1][j];
                    }
                }else {
                    if(i==0){  //初始化边界
                        dp[i][j] = nums2[i];
                    }else {
                        dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-nums1[i]]+nums2[i]);
                    }

                }
            }
        }
        return dp[len1-1][sum];
    }

    /**
     * 2. 暴力解法  使用回溯遍历  时间复杂度为 2的n次方
     */
}
